package us.luosl.lintcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 59. 最接近的三数之和
 * 中文English
 * 给一个包含 n 个整数的数组 S, 找到和与给定整数 target 最接近的三元组，返回这三个数的和。
 *
 * 样例
 * 例1:
 *
 * 输入:[2,7,11,15],3
 * 输出:20
 * 解释:
 * 2+7+11=20
 * 例2:
 *
 * 输入:[-1,2,1,-4],1
 * 输出:2
 * 解释:
 * -1+2+1=2
 * 挑战
 * O(n^2) 时间, O(1) 额外空间。
 *
 * 注意事项
 * 只需要返回三元组之和，无需返回三元组本身
 */
public class Solution59 {
    /**
     * @param numbers: Give an array numbers of n integer
     * @param target: An integer
     * @return: return the sum of the three integers, the sum closest target.
     */
    public int threeSumClosest(int[] numbers, int target) {
        // write your code here
        Set<Integer> used = new HashSet<>();
        int result = 0;
        for(int j=0; j<3; j++){
            Integer diff = null;
            int bestSum = 0;
            int usedIdx = -1;
            for(int i=0; i<numbers.length; i++){
                if(used.contains(i)){
                    continue;
                }
                int sum = result + numbers[i];
                int currentDiff = Math.abs(sum - target);
                if(null == diff || currentDiff < diff){
                    diff = currentDiff;
                    usedIdx = i;
                    bestSum = sum;
                }
            }
            used.add(usedIdx);
            result = bestSum;
        }
        return result;
    }

    public static void main(String[] args) {
        int res = new Solution59().threeSumClosest(new int[]{1,0,-1,0,-2,2,21,-15}, -20);
        System.out.println();
    }
}